package com.wubotao.algorithm;

import java.util.Arrays;

public class MergeSort {
	
	public static void sort(int[] data) {
		msort(data, 0, data.length-1);
	}
	

	public static void msort(int[] data, int left, int right) {
		if (left < right) { 
			int center = (left + right) / 2; 
			
			msort(data, left, center); 
			msort(data, center + 1, right); 
			
			merge(data, left, center, right);
		}
	}

	private static void merge(int[] data, int left, int center, int right) {

		int[] tmpArr = new int[data.length];
		int mid = center + 1; 
		int third = left;
		int tmp = left;
		while (left <= center && mid <= right) { 
			if (data[left] <= data[mid]) {
				tmpArr[third++] = data[left++];
			} else {
				tmpArr[third++] = data[mid++];
			}
		}
		while (mid <= right) {
			tmpArr[third++] = data[mid++];
		}
		while (left <= center) {
			tmpArr[third++] = data[left++];
		}
		while (tmp <= right) {
			data[tmp] = tmpArr[tmp++];
		}
		System.out.println(Arrays.toString(data));
	}

	public static void main(String[] args) {
		int arr[] = { 49, 38, 65, 97, 76, 13, 27 };
		sort(arr);
		System.out.println(Arrays.toString(arr));
	}
}
